#!/usr/bin/env python3
# -*-coding: utf-8-*-
'''一个有序数组A，另一个无序数组B，请打印B中的所有不在A中的数，A数 组长度为N，B数组长度为M
'''
import random

def generate_random_array(max_size: int, max_value: int) -> list:
    length = random.randint(0, max_size)
    arr = []
    for i in range(length):
        arr.append(random.randint(0, max_value))
    return arr
'''
对于数组B中的每一个数，都在A中通过二分的方式找一下；
'''
def get_all_not_included_in_a(a: list, b: list) -> list:
    res =[]
    for i in range(len(b)):
        in_a = False
        pl = 0
        pr = len(a) -1
        while pl <= pr:
            mid = pl + ((pr - pl) >> 1)
            if b[i] == a[mid] :
                in_a = True
                break
            elif b[i] < a[mid]:
                pr = mid -1
            else :
                pl = mid + 1
        if in_a is False:
            res.append(b[i])
    return res

'''
先把数组B排序，然后用类似外排的方式打印所有在A中出现的数
'''
def get_all_not_included_in_a1(a: list, b: list) -> list:
    res = []
    b.sort()
    i = j = 0
    while i < len(a) and j < len(b):
        if b[j] == a[i] :
            j += 1
        elif b[j] < a[i]:
            res.append(b[j])
            j += 1
        else :
            i += 1
    while j < len(b):
        res.append(b[j])
        j += 1

    return res


def is_equal(a: list, b: list) -> bool:
    if len(a) != len(b): return False
    tmp_dict = {}
    for i in a:
        if i not in tmp_dict:
            tmp_dict[i] = 0   #如果不在字典里面，就加入字典，初始值0
        tmp_dict[i] += 1      #如果已经存在，说明原始数组有多个重复的值，个数加1
    for j in b:
        if j not in tmp_dict: return False  # b 中的元素完全不在a中
        tmp_dict[j] -= 1
        if tmp_dict[j] < 0: return False    # b 中的元素个数与a中不符
    return True



def comparator(a: list, b: list) -> list:
    res = []
    for i in b:
        in_a = False
        for j in a:
            if i == j:
                in_a = True
                break
        if in_a == False:
            res.append(i)
    return res

def main():
    testTime = 300000
    sortedArrayMaxSize = 300
    unsortedArrayMaxSize = 10
    maxValue = 100
    succeed = True

    for i in range(testTime + 1):
        A = generate_random_array(sortedArrayMaxSize, maxValue)
        B = generate_random_array(unsortedArrayMaxSize, maxValue)
        A.sort()
        res1 = get_all_not_included_in_a(A, B)
        res2 = comparator(A, B)
        if not is_equal(res1, res2):
            succeed = False
            break
    if succeed is True:
        print("Nice!")
    else:
        print("Fucking fucked!")
        print('A, B')
        print(A)
        print(B)
        print('res1, res2')
        print(res1)
        print(res2)
main()